# 多数元素
class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        def majority_element_rec(lo, hi) -> int:
            # 基本情况；大小为1的数组中唯一的元素就是多数元素
            if lo == hi:
                return nums[lo]

            # 在左右两边进行递归
            mid = (hi - lo) // 2 + lo
            left = majority_element_rec(lo, mid)
            right = majority_element_rec(mid + 1, hi)

            # 如果两部分在多数元素上达成一致，则返回该元素。
            if left == right:
                return left

            # 否则，统计每个元素的数量并返回“较多者”。
            left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
            right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)

            return left if left_count > right_count else right

        return majority_element_rec(0, len(nums) - 1)

#参考：力扣官方题解

solution = Solution()
nums = [2, 2, 1, 1, 1, 2, 2]
result = solution.majorityElement(nums)
print(f"多数元素是: {result}")